import numpy as np

def bresenham(x1, y1, x2, y2):
    """
    Bresenham algorithm in all four quadrants
    :param x1, y1: coordinate of the lower left point
    :param x2, y2: coordinate of the upper right point
    :return: a list of the points on the line segment from (x1, y1) to (x2, y2)
                        (x2, y2)
    -----------------/--------------------------
    |              /                            |
    -------------/------------------------------
    |          /                                |
    _________/___________________________________
    |      /                                    |
    _____/______________________________________
    |  /                                        |
    _/__________________________________________
    (x1,y1)
    In the condition of slope ~ (0, 1], just compute the decision parameter P,
    initial state P1 = 2dy-dx, A = 2dy, B = 2dy - 2dx. Use these values to update
    the (xk, yk) is enough, but for all the slope, we need two tricks:
    1. |m| <= 1, no interchange
    2. |m| > 1, interchange x and y
    3. sign(m) > 0, increase x(y) every time depend on the interchange
    4. sign(m) <= 0, decrease x(y) every time depend on the interchange
    """

    # compute P, P1, and which condition is the line segment is in
    x = x1
    y = y1
    dx = np.abs(x2 - x1)
    dy = np.abs(y2 - y1)
    sx = np.sign(x2 - x1)
    sy = np.sign(y2 - y1)
    if dy - dx > 0:
        dx, dy = dy, dx
        interchange = True
    else:
        interchange = False


    E = 2*dy - dx
    A = 2*dy
    B = 2*(dy - dx)

    # compute the point list, defined by x_bres and y_bres
    x_bres, y_bres = [], []
    x_bres.append(x)
    y_bres.append(y)
    for _ in range(1, int(dx)):
        if E > 0:
            y += sy
            x += sx
            E += B
        else:
            if interchange:
                y += sy
            else:
                x += sx
            E += A

        x_bres.append(x)
        y_bres.append(y)
    return zip(x_bres, y_bres)
